package algorithm.recursion.basic;

/**
 * 项目名称: god
 * 包 名 称: algorithm.recursion.basic
 * 类 名 称: Hanoi
 * 类 描 述: TODO
 * 创建时间: 2020/7/8 9:22 下午
 * 创 建 人: Justice
 * T(n) = 2 * [2 * T(n - 2) + O(1)] + O(1)
 * T(n) = 2^2 * [2 * T(n - 3) + O(1)] + 2 * O(1) + O(1)
 * T(n) = 2^3 * T(n - 3) + (2^2 + 2^1 + 2^0) * O(1)
 * T(n) = 2^(n - 1) * O(1) + (2^(n-2) + ... + 2^2 + 2^1 + 2^0) * O(1)
 * T(n) = [2^(n - 1)+ 2^(n-2) + ... + 2^2 + 2^1 + 2^0] * O(1)
 * T(n) = (2^n - 1) * O(1)
 */
public class Hanoi {
    // 将n个盘子从A移动到C
    public static void hanoi(int n, String p1, String p2, String p3) {
        if (n == 1) {
            move(n, p1, p3);
            return;
        }
        // 将n-1个盘子从A移动到B
        hanoi(n - 1, p1, p3, p2);
        // 将第n个盘子从A移动到C
        move(n, p1, p3);
        // 将n-1个盘子从B移动到C
        hanoi(n - 1, p2, p1, p3);
    }

    public static void move(int m, String from, String to) {
        // 将m号盘子从 from 移动到 to
        System.out.println("将" + m + "号盘子从" + from + "移动到" + to);
    }
}
